Relational and object-relational database management systems store information in tables in a database. To retrieve data, queries that request data are submitted to a database server, which computes the queries and returns the data requested. Query statements submitted to the database server should conform to the syntactical rules of a particular query language. One popular query language, known as the Structured Query Language (SQL), provides users a variety of ways to specify information to be retrieved.
A query submitted to a database server is evaluated by a query optimizer. Based on the evaluation, the query optimizer generates an execution plan that is optimized for efficient execution. The optimized execution plan may be based on a rewrite of the query into a semantically equivalent but more efficient form.
For example, a query may be rewritten when it contains logically unnecessary operations. This type of inefficiency occurs in queries for many reasons. For example, database users often do not write queries directly, but rather utilize “middleware” software programs. Such middleware software programs receive declarative input from the user and automatically generate queries based on the declarative input. Often, the “middleware” software does not check whether the generated queries are optimized. In addition, a human application developer may also introduce inefficient queries.
SQL supports join operations, which combine the contents of two tables. Specific join operations will be described in greater detail herein. Unnecessary joins are undesirable because join operations are expensive operations for a database system to execute. Therefore, it is desirable to develop techniques for rewriting queries to eliminate tables from queries by removing join operations in the queries which contain the tables when such removals have no logical impact on the query results.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.